struct ListNode
{
    int val;
    struct ListNode *next;
};

/**
 * 解法1：双指针，不断交互尾部两个node，最后达到反转
 */
struct ListNode *reverseList(struct ListNode *head)
{

    // A->B->C
    // A      B     C
    // head  curr
    // B      A     C
    // head         curr

    if (head == 0)
    {
        return head;
    }

    struct ListNode *node1 = head;
    struct ListNode *node2 = head->next;

    struct ListNode *newHeaderNode = head;

    int isfirst = 0;

    while (head->next != 0)
    {
        // 当头布局不为空时
        if (node2->next != 0)
        {
            node1 = node2;
            node2 = node2->next;
        }
        else
        {
            if (isfirst == 0)
            {
                newHeaderNode = node2;
                isfirst = 1;
            }

            // 交换node1 node2
            node2->next = node1;
            node2->next->val = node1->val;

            node1->next = 0;

            node1 = head;
            node2 = head->next;
        }
    }

    return newHeaderNode;
};

/**
 * 解法2  双指针 ，设定新链表，从旧表头开始取不断放入新链表后面
 */
struct ListNode *reverseList(struct ListNode *head)
{
    struct ListNode *newHead=NULL;//不设置会有野指针

    struct ListNode *curr = head;
    struct ListNode *next=NULL;
    while (curr != 0)
    {
        if (newHead == 0)
        {
            newHead = curr;
            curr = curr->next;
            newHead->next = NULL;
        }
        else
        {   next = curr->next;
          
            curr->next = newHead;
            newHead = curr;

            curr = next;
        }
    }
    return newHead;
};

/**
 * 解法2 设定新链表
*/

struct ListNode *reverseList(struct ListNode *head)
{
   struct ListNode *firstNode = NULL;
   //如何反转：1. 设定新链表 firstNode， head指向旧链表头部，将旧链表头指向新链表头部，最后旧链表移动到下一个位置
    while(head !=NULL){
       struct ListNode *next =  head->next;
        head->next = firstNode;
        firstNode = head;
        head = next;
    }

    return firstNode;
};